package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。
 *
 * @author gezhangyuan
 */
public class DicesSum {

    static List<List<Integer>> nums = new ArrayList<List<Integer>>();

    public static void main(String[] args) {
        List<Map.Entry<Integer, Double>> result = dicesSum(4);
        result.forEach((e) -> System.out.println(e.getKey() + ":" + e.getValue()));
    }

    public static List<Map.Entry<Integer, Double>> dicesSum(int n) {
        get(new ArrayList<Integer>(), n);
        double total = Math.pow(6, n);
        Map<Integer, Integer> rate = new HashMap<Integer, Integer>();

        for (List<Integer> num : nums) {
            int sum = 0;
            for (Integer numItem : num) {
                sum += numItem;
            }
            Integer old = rate.get(sum);
            old = old == null ? 0 : old;
            rate.put(sum, ++old);
        }

        Map<Integer, Double> rate2 = new HashMap<Integer, Double>();
        rate.forEach((k, v) -> rate2.put(k, v / total));
        return new ArrayList<>(rate2.entrySet());
    }

    public static void get(List<Integer> suf, int remain) {
        if (remain == 0) {
            nums.add(suf);
            return;
        }
        for (int i = 1; i < 7; i++) {
            List<Integer> s = new ArrayList<Integer>(suf);
            s.add(i);
            get(s, remain - 1);
        }
    }
}
